#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>
#include <stdint.h>
#include <signal.h>
#include <string.h>

#define TEST 0

typedef float real;

typedef struct
{
    unsigned int id;
    real x;
    real y;
} Data;

real dises[2500 * 2500];

real dis(uint16_t *s, uint16_t count)
{
    uint16_t i;
    real r = 0;
    for(i = 0; i < count; i++)
    {
        uint16_t j = i ? i - 1 : count - 1;
        r += dises[s[i] * 2500 + s[j]];
    }
    return r;
}

volatile sig_atomic_t cont = 1;
void term(int signum)
{
    cont = 0;
}

int main()
{
    Data datas[2502];
    uint16_t datas_count = 0, i, j, p = 1000, ii;
    real k = 0.99;
    uint16_t s[2500], s_min[2500];
    real e, e_min;
    real t;
    struct sigaction action;
#if TEST
    clock_t st;
#endif

    srand(time(NULL));
    memset(dises, 0, sizeof dises);

    memset(&action, 0, sizeof(struct sigaction));
    action.sa_handler = term;
    sigaction(SIGTERM, &action, NULL);

#if TEST
    sigaction(SIGINT, &action, NULL);

    st = clock();
    for(i = 0; i < 2500; i++)
    {
        datas[datas_count].id = i + 1;
        datas[datas_count].x = rand() * 2e5 / RAND_MAX - 1e5;
        datas[datas_count++].y = rand() * 2e5 / RAND_MAX - 1e5;
    }
#else
    while(scanf("%u%f%f",&datas[datas_count].id,&datas[datas_count].x,&datas[datas_count].y))
        datas_count++;
#endif


    for(i = 0; i < datas_count; i++)
    {
        for(j = 0; j < datas_count; j++)
        {
            real dx,dy;
            if(i == j)
                continue;
            dx = datas[i].x - datas[j].x;
            dy = datas[i].y - datas[j].y;
            dises[i * 2500 + j] = sqrt(dx * dx + dy * dy);
        }
    }
#if TEST
    printf("read time: %.1fs\n", (real)(clock() - st) / CLOCKS_PER_SEC);
    st = clock();
#endif

    for(i = 0; i < datas_count; i++)
        s[i] = i;
    memcpy(s_min, s, sizeof(uint16_t) * datas_count);
    e_min = e = dis(s, datas_count);
    t = 1;
    ii = 0;
    for(t = 1, ii = 0; t > 0 && ii < p && cont; t *= k)
    {
        uint16_t n1, n2;
        uint16_t sn[2500];
        real en;

        n1 = rand() % (datas_count + 1);
        n2 = rand() % datas_count;
        if(n2 >= n1)
            n2++;
        else
        {
            uint16_t t = n1;
            n1 = n2;
            n2 = t;
        }

        if(n1)
            memcpy(sn, s, sizeof(uint16_t) * n1);
        for(i = n1; i < n2; i++)
            sn[i] = s[n1 + n2 - i - 1];
        if(n2 < datas_count)
            memcpy(sn + n2, s + n2, sizeof(uint16_t) * (datas_count - n2));
        en = dis(sn, datas_count);
        if(en < e || (real)rand() / RAND_MAX < exp((e - en) / t))
        {
            e = en;
            memcpy(s, sn, sizeof(uint16_t) * datas_count);
        }
        if(e >= e_min)
            ii++;
        else
        {
            ii = 0;
            e_min = e;
            memcpy(s_min, s, sizeof(uint16_t) * datas_count);
        }
    }
#if TEST
    printf("%-10g%-5hu  %.2f  %.1fs\n", k, p, e_min, (real)(clock() - st) / CLOCKS_PER_SEC);
#else
    for(i = 0; i < datas_count; i++)
        printf("%u\n", datas[s_min[i]].id);
#endif

    return 0;
}
